package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}18:34
 */
public class LeetCode1143 {
    // LCS算法
    public int longestCommonSubsequence(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0)
            return 0;
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        //为了便于理解
        char[] text1 = new char[str1.length() + 1];
        text1[0] = '/';
        char[] text2 = new char[str2.length() + 1];
        text2[0] = '/';
        for (int i = 1; i < text1.length; i++){
            text1[i] = str1.charAt(i - 1);
        }
        for (int i = 1; i < text2.length; i++){
            text2[i] = str2.charAt(i - 1);
        }

        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (text1[i] == text2[j]) {
                    dp[i][j] = dp[i][j - 1] + 1;
                } else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[str1.length()][str2.length()];
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode1143().longestCommonSubsequence("abcde", "ace"));
    }
}
